package com.gitee.feizns.explore.data_structure.linked_list.singly.addTwoNumbers;

import com.gitee.feizns.explore.data_structure.linked_list.singly.ListNode;

import java.util.Stack;

/**
 * @author feizns
 * @since 2020/3/6
 */
public class AddTwoNumbers {

    public static void main(String[] args) {
        addTwoNumbers(create1(), create2()).print();
    }

    private static ListNode create1() {
        ListNode ret = new ListNode(1);
        ret.next = new ListNode(0);
        ret.next.next = new ListNode(9);
        return ret;
    }

    private static ListNode create2() {
        ListNode ret = new ListNode(9);
        ret.next = new ListNode(9);
        ret.next.next = new ListNode(9);
        return ret;
    }

    public static ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        Stack<ListNode> s1 = reverse(l1);
        Stack<ListNode> s2 = reverse(l2);
        Stack<Integer> ret = new Stack<>();
        int carry = 0;
        while ( !s1.isEmpty() || !s2.isEmpty() ) {
            int curt = carry;
            if ( !s1.isEmpty() )
                curt += s1.pop().val;
            if ( !s2.isEmpty() )
                curt += s2.pop().val;
            ret.add(curt % 10);
            carry = curt / 10;
        }
        if ( carry != 0 )
            ret.add(carry);
        return create(ret);
    }

    private static ListNode create(Stack<Integer> stack) {
        if ( !stack.isEmpty() ) {
            ListNode ret = new ListNode(stack.pop());
            ret.next = create(stack);
            return ret;
        }
        return null;
    }

    private static Stack<ListNode> reverse(ListNode node) {
        Stack<ListNode> ret = new Stack<>();
        for (ListNode tmp = node; tmp != null; tmp = tmp.next)
            ret.add(tmp);
        return ret;
    }

}
